/**
 * @author tmh
 * @date 2024/9/24 17:02
 * @description
 */
public class T31下一个排列 {
    public void nextPermutation(int[] nums) {
        //找到第一个上涨的数字
        int index = nums.length - 1;
        boolean flag = true;
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i - 1] > nums[i]) {
                index = i - 1;
                flag = false;
                break;
            }
        }
        if (flag) {
            swap(nums, 0);
        } else {
            for (int i = nums.length - 1; i >= 0; i--) {
                if (nums[i] > nums[index]) {
                    int temp = nums[i];
                    nums[i] = nums[index];
                    nums[index] = temp;
                    //这里还需要重新swap下
                    swap(nums,index+1);
                    break;
                }
            }
        }
    }

    private void swap(int[] nums, int start) {
        int len = nums.length;
        for (int i = start, j = len - 1; i < j; i++, j--) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
}
